package oj_leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSum2 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        for (int i = 1; i <= candidates.length; i++) {
            res.addAll(combinationSum(target, candidates, 0, i));
        }
        return res;
    }

    public List<List<Integer>> combinationSum(int target, int[] candidates, int currIndex, int n) {
        List<List<Integer>> res = new ArrayList<>();
        if (n == 1) {
            for (int i = currIndex; i < candidates.length; i++) {
                if (candidates[i] == target) {
                    res.add(new ArrayList(Arrays.asList(target)));
                    break;
                }
            }
            return res;
        }

        for (int i = currIndex; i < candidates.length - n + 1; i++) {
            int curr = candidates[i];
            int need = target - curr;
            if (need <= 0) {
                break;
            }
            List<List<Integer>> nr = combinationSum(need, candidates, i + 1, n - 1);
            for (List<Integer> list : nr) {
                list.add(curr);
            }
            res.addAll(nr);
            while (i < candidates.length - 1 && candidates[i + 1] == curr) {
                i++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        new CombinationSum2().combinationSum2(new int[]{2, 5, 2, 1, 2}, 5);

    }
}
